package leetcode.lcp;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution2 implements IDebug {

	class Node {

		private int begin;
		private int end;
		private int mid;
		private boolean red;
		private Boolean bkCache;
		private Node left;
		private Node right;

		public Node(int begin, int end) {
			this.begin = begin;
			this.end = end;
			this.mid = ((end - begin) >> 1) + begin;
			this.red = false;
		}

		public Node getLeft() {
			if (this.left == null) {
				this.left = new Node(this.begin, this.mid);
			}
			return this.left;
		}

		public Node getRight() {
			if (this.right == null) {
				this.right = new Node(this.mid + 1, this.end);
			}
			return this.right;
		}

		public void color(int l, int r, boolean red) {
			if (l <= this.begin && this.end <= r) {
				this.red = red;
				this.bkCache = red;
				return;
			}
			this.pushDown();
			if (r <= this.mid) {
				this.getLeft().color(l, r, red);
			} else if (l > this.mid) {
				this.getRight().color(l, r, red);
			} else {
				this.getLeft().color(l, this.mid, red);
				this.getRight().color(this.mid + 1, r, red);
			}
			this.red = this.getLeft().red || this.getRight().red;
		}

		public boolean blue(int l) {
			if (l == this.begin && l == this.end) {
				return this.red;
			}
			this.pushDown();
			if (l <= this.mid) {
				return this.getLeft().blue(l);
			} else if (l > this.mid) {
				return this.getRight().blue(l);
			}
			return true;
		}

		private void pushDown() {
			if (this.bkCache != null) {
				Node l = this.getLeft();
				l.red = this.red;
				l.bkCache = this.bkCache;
				Node r = this.getRight();
				r.red = this.red;
				r.bkCache = this.bkCache;
				this.bkCache = null;
			}
		}

	}

	private Node segtree;

	public int getNumber(TreeNode root, int[][] ops) {
		segtree = new Node(0, (int) (1e9 + 1));
		for (int i = 0; i < ops.length; i++) {
			int[] op = ops[i];
			int type = op[0], x = op[1], y = op[2];
			segtree.color(x, y, type == 1);
		}
		return this.find(root);
	}

	private int find(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int ans = 0;
		int val = root.val;
		if (this.segtree.blue(val)) {
			ans += 1;
		}
		ans += this.find(root.left);
		ans += this.find(root.right);
		return ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
